package gold.gold05;

import java.util.HashMap;
import java.util.Map;

/**
 * 双指针也叫滑动窗?
 */
public class S1718最短超串 {
    /**
     * 97, 算是双指针里判断条件比较复杂的, 写了很久才优化成这样。
     * 用一个二维数组(这种场合其实map更合适)存储small中每个元素的位置的最大值和最小值。行不通。
     * 双指针, 然后用一个map存储每个元素是否被发现
     */
    public int[] shortestSeq(int[] big, int[] small) {
        if(big.length == 0 | small.length == 0) return new int[0];
        int tarLen = small.length;
        Map<Integer, Integer> recoMap = new HashMap<>(tarLen); // 记录每个元素出现的次数。
        for(int s: small) recoMap.put(s, 0);
        int recordedNum = 0;
        int fast = 0, slow = 0;
        int[] res = new int[]{0, big.length + 1}; // 注意是big.length
        // 在快指针前进的循环中套上慢指针前进的部分, 通过完全记录来触发。
        for(; fast < big.length; fast++){
            int fastStat = recoMap.get(big[fast]) == null? -1 : recoMap.get(big[fast]);
            if(fastStat == 0){
                recoMap.put(big[fast], 1);
                recordedNum++;
            }else if(fastStat > 0){
                recoMap.put(big[fast], fastStat + 1);
            }
            while(recordedNum == tarLen){
                if(fast - slow < res[1] - res[0]){
                    // 更新最小间距
                    res[1] = fast;
                    res[0] = slow;
                }
                int slowStat = recoMap.get(big[slow]) == null? -1 : recoMap.get(big[slow]);

                if(slowStat == 1){
                    recoMap.put(big[slow], 0);
                    recordedNum --;
                }else if(slowStat > 1){
                    recoMap.put(big[slow], slowStat - 1);
                }
                slow ++;
            }
        }
        return res[1] - res[0] == big.length + 1? new int[0] : res;

    }
}
